#FA.rb 2019.10.22
class FARules < Struct.new(:statement, :character, :next_statement)
	def apply_to(statement, character)
		self.statement == statement && self.character == character
	end
	def follow
		next_statement
	end
end

class DFARulesbook < Struct.new(:rules)
	def next_statement(statement, character)
		rules_for(statement, character).follow
	end
	def rules_for(statement, character)
		rules.detect {|rule| rule.apply_to(statement, character)}
	end
end

# rule_book = DFARulesbook.new([FARules.new(1, 'c', 2), FARules.new(1, 'b', 1), FARules.new(2, 'c', 1), FARules.new(2, 'b', 2)])
# puts rule_book.next_statement(1, 'c')
# puts rule_book.next_statement(2, 'c')
# puts rule_book.next_statement(1, 'b')
# puts rule_book.next_statement(2, 'b')

class DFA < Struct.new(:current_state, :accept_state, :rules_book)
	def accepting?
		accept_state.include?(current_state)
	end
	def read_character(char)
		self.current_state = rules_book.next_statement(current_state, char)
	end
	def read_string(string)
		string.chars.each do |char|
			read_character(char)
		end
	end
end

# rule_book = DFARulesbook.new([FARules.new(1, 'c', 2), FARules.new(1, 'b', 1), FARules.new(2, 'c', 1), FARules.new(2, 'b', 2)])
# dfa = DFA.new(1, [1, 2], rule_book)
# puts dfa.accepting?
# puts dfa.read_character('c')
# puts dfa.read_character('c')
# dfa.read_string('ccb'); puts dfa.accepting?
# dfa.read_string('cb');  puts dfa.accepting?

class DFADesign < Struct.new(:current_state, :accept_state, :rules_book)
	def design
		DFA.new(current_state, accept_state, rules_book)
	end
	def accepts?(string)
		design.tap{|fda| fda.read_string(string)}.accepting?
	end
end

# rule_book = DFARulesbook.new([FARules.new(1, 'c', 2), FARules.new(1, 'b', 1), FARules.new(2, 'c', 1), FARules.new(2, 'b', 2)])
# dfa_des = DFADesign.new(1, [2], rule_book)
# puts dfa_des.accepts?('cc')
# puts dfa_des.accepts?('ccbc')

require 'set'
class NFARulesbook < Struct.new(:rules)
	def next_states(states, character)
		states.flat_map{|state| follow_rules_for(state, character)}.to_set
	end
	def follow_rules_for(state, character)
		rules_for(state, character).map(&:follow)
	end
	def rules_for(state, character)
		rules.select{ |rule| rule.apply_to(state, character)}
	end
end

class NFA < Struct.new(:current_states, :accept_states, :rules_book)
	def accepting?
		(current_states & accept_states).any?
	end
	def read_character(character)
		self.current_states = rules_book.next_states(current_states, character)
	end
	def read_string(string)
		string.chars.each do |char|
			read_character(char)
		end
	end
end

# rules_book = NFARulesbook.new([FARules.new(1, 'b', 1), FARules.new(1, 'a', 2), FARules.new(1, 'a', 3)])
# puts rules_book.next_states(Set[1], 'a')
# puts rules_book.next_states(Set[1, 2], 'b')
# nfa = NFA.new(Set[1], [3], rules_book)
# nfa.read_character('b'); puts nfa.accepting?
# nfa.read_string('bbbbba'); puts nfa.accepting?

class NFADesign < Struct.new(:current_states, :accept_states, :rules_book)
	def design
		NFA.new(Set[current_states], accept_states, rules_book)
	end
	def accepts?(string)
		design.tap{|nfa| nfa.read_string(string)}.accepting?
	end
end

# rules_book = NFARulesbook.new([FARules.new(1, 'b', 1), FARules.new(1, 'a', 2), FARules.new(1, 'a', 3)])
# nfa_design = NFADesign.new(1, [3], rules_book)
# puts nfa_design.accepts?('bbbbb')
# puts nfa_design.accepts?('bbbba')

class NFARulesbook
	def follow_free_moves(states)
		more_states = next_states(states, nil)
		if more_states.subset?(states)
			states
		else 
			follow_free_moves(more_states + states)
		end
	end
end

class NFA
	def current_states
		rules_book.follow_free_moves(super)
	end
end

# rules_book = NFARulesbook.new([FARules.new(1, nil, 2), FARules.new(1, nil, 4), FARules.new(2, 'a', 3), FARules.new(3, 'a', 2), FARules.new(4, 'a', 5), FARules.new(5, 'a', 6), FARules.new(6, 'a', 4)])
# nfa = NFADesign.new(Set[1], [2,4], rules_book)
# puts nfa.accepts?('aaaaa')
# puts nfa.accepts?('aaaa')
# puts nfa.accepts?('aaa')
# puts nfa.accepts?('aa')
# puts nfa.accepts?('a')


module Pattern
	def bracket(outer_precedence)
		if precedence < outer_precedence
			'(' + to_s + ')'
		else
			to_s
		end
	end
	def inspect
		"<#{self}>"
	end
end

class Empty
	include Pattern

	def precedence
		3
	end
	def to_s
		''
	end
end

class Literal < Struct.new(:character)
	include Pattern
	
	def precedence
		3
	end
	def to_s
		character
	end
end

class Concatenate < Struct.new(:first, :last)
	include Pattern
	
	def precedence
		1
	end
	def to_s
		[first, last].map{ |pattern| pattern.bracket(precedence)}.join 
	end
end

class Or < Struct.new(:left, :right)
	include Pattern
	
	def precedence
		0
	end
	def to_s
		[left, right].map{ |pattern| pattern.bracket(precedence)}.join('|')
	end
end

class Repeat < Struct.new(:pattern)
	include Pattern
	
	def precedence
		2
	end
	def to_s
		pattern.bracket(precedence) + '*'
	end
end

#puts Repeat.new(Or.new(Concatenate.new(Literal.new('a'), Literal.new('b')), Literal.new('c')))

class Empty
	def to_nfa_design
		current_state = Object.new
		accept_state  = [current_state]
		rules_book    = NFARulesbook.new([]) 
		
		NFADesign.new(current_state, accept_state, rules_book)
	end
end

class Literal
	def to_nfa_design
		current_state = Object.new
		accept_state  = Object.new
		rules_book = NFARulesbook.new([FARules.new(current_state, character, accept_state)])
		
		NFADesign.new(current_state, [accept_state], rules_book)
	end
end

# nfa_design = Empty.new.to_nfa_design
# puts nfa_design.accepts?('')
# puts nfa_design.accepts?('a')
#nfa_design = Literal.new('a').to_nfa_design
#puts nfa_design.accepts?('a')
#puts nfa_design.accepts?('')

class Concatenate
	def to_nfa_design
		first_nfa_design = first.to_nfa_design
		last_nfa_design  = last.to_nfa_design
		
		current_states = first_nfa_design.current_states
		accept_states  = last_nfa_design.accept_states
		
		rules = first_nfa_design.rules_book.rules + last_nfa_design.rules_book.rules
		extra_rules = first_nfa_design.accept_states.map{|state| FARules.new(state, nil, last_nfa_design.current_states)}
		
		rules_book = NFARulesbook.new(rules + extra_rules)
		
		NFADesign.new(current_states, accept_states, rules_book)
	end
end

module Pattern
	def match?(string)
		to_nfa_design.accepts?(string)
	end
end

# pattern = Concatenate.new(Literal.new('a'), Literal.new('b'))
# puts pattern.to_nfa_design.accepts?('ab')
# puts pattern.match?('abb')
# pattern = Concatenate.new(Literal.new('a'), Concatenate.new(Literal.new('a'), Literal.new('b')))
# puts pattern.to_nfa_design.accepts?('aab')
# puts pattern.match?('aa')

class Or
	def to_nfa_design
		left_nfa_design  = left.to_nfa_design
		right_nfa_design = right.to_nfa_design
		
		current_states = Object.new
		accept_states  = left_nfa_design.accept_states + right_nfa_design.accept_states
		
		rules = left_nfa_design.rules_book.rules + right_nfa_design.rules_book.rules
		extra_rules = [left_nfa_design, right_nfa_design].map{|state| FARules.new(current_states, nil, state.current_states)}
		rules_book = NFARulesbook.new(rules + extra_rules)
		
		NFADesign.new(current_states, accept_states, rules_book)
	end
end

# pattern = Or.new(Literal.new('a'), Literal.new('b'))
# puts pattern.match?('a')
# puts pattern.match?('b')
# puts pattern.match?('c')

class Repeat
	def to_nfa_design
		pattern_nfa_design = pattern.to_nfa_design
		
		current_states = Object.new
		accept_states  = pattern_nfa_design.accept_states + [current_states]

		rules = pattern_nfa_design.rules_book.rules
		extra_rules = pattern_nfa_design.accept_states.map{|state| FARules.new(state, nil, pattern_nfa_design.current_states)} + [FARules.new(current_states, nil, pattern_nfa_design.current_states)]
		rules_book  = NFARulesbook.new(rules + extra_rules)
		
		NFADesign.new(current_states, accept_states, rules_book)
	end
end

# pattern = Repeat.new(Literal.new('a'))
# puts pattern.match?('aaa')
# puts pattern.match?('aa')
# puts pattern.match?('a')
# puts pattern.match?('')
# puts pattern.match?('bbbb')
